\onlyLong{\subsection{A  Mapping Lemma} }
\label{sec:mapping}

{We first prove a ``mapping'' lemma for the random vertex partition model, which we will use in our Conversion theorem (cf.\ Theorem~\ref{thm:translation}).}
Consider an input  graph $G=(V,E)$ that is partitioned (according to the random vertex partition model) among the $k$ machines in $N = \{p_1,\dots,p_k\}$ of the network. Let $|V| = n$ and $|E| = m$. We will assume (without loss of generality) throughout that $n \geq k$.
We say that a vertex $v$ of $G$ is mapped to a machine $h$ of $N$ if $v$ is assigned to $N$, i.e., $h$ is the home machine of $v$ (cf. Section \ref{sec:model}).
We say that an edge $e =(u,v)$ of $G$ is {\em mapped} to a link $(p_i,p_j)$ of the $k$-machine network, if $u$ is mapped to $p_i$
and $v$ is mapped to $v_j$ or vice versa. The following Mapping Lemma gives a concentration bound on the number of edges mapped to
any link of the  network. %\onlyShort{\footnote{The full proofs are in the full paper in the appendix.}}
\onlyShort{ Its proof uses Bernstein's inequality \cite{panconesi} and is deferred to the full paper.}

\begin{lemma}[Mapping Lemma] \label{lem:mapping}
Let an $n$-node, $m$-edge graph $G$ be partitioned among the $k$ machines in  $N = \{p_1,\dots,p_k\}$, according
to the random vertex partition model (assume $n \geq k$). 
%Let the number of edges mapped to a link $(p_i,p_j)$ for any $i$ and $j$ ($1 \leq i, j \leq k$).
Then with high probability (whp) (i.e., with probability at least $1 - 1/n$), the following bounds hold:
\begin{compactdesc}
  \item[(1)] The number of vertices of $G$ mapped to any machine is $\tilde{O}(n/k)$.
  \item[(2)] The number of edges of $G$ mapped to any link of the network is $\tilde{O}(m/k^2 + \Delta/k)$, where $\Delta$ is the maximum node degree of $G$.%\danupon{We should have ``+1'' term somewhere or say that $k\leq \max{\sqrt{m}, \Delta}$}
\end{compactdesc}
\end{lemma}


 % \begin{comment}
\onlyLong{%
\begin{proof}

  \noindent  {\bf (1)}  This follows easily from a direct Chernoff bound application. Since each vertex of $G$ is mapped independently
and uniformly to the set of $k$ machines, the expected number of vertices mapped to a machine is $n/k$. The concentration
follows from a standard Chernoff bound \cite{panconesi}. 

\medskip
\noindent  {\bf (2)}  We first note that we cannot directly apply a Chernoff bound to show concentration
on the number of edges mapped, as these are not independently distributed. We  show the bound in two steps:
\begin{compactenum}
\item (a) We first show a concentration bound on the total degree of the vertices assigned to any machine; 
\item (b) then we bound the number of edges assigned to any link.
\end{compactenum}

To show (a) we use {\em Bernstein's inequality} \cite{panconesi}. Fix a machine $p$.
 Let random variable $X^p_i$ be defined as follows: $X^p_i = d(v_i)$ ($d(v_i)$ is the degree of $v_i$) if vertex $v_i$ is assigned to machine $p$, otherwise $X^p_i = 0$. Let $X^p= \sum_{i=1}^n X^p_i$ denote the total degree of the vertices assigned to machine $p$; in other words, it is the total number of edges that have at least one endvertex assigned to machine $p$.
 We have $E[X^p_i] = d(v_i)/k$ and $E[X^p] = \sum_{i=1}^n E[X^p_i] = \sum_{i=1}^n d(v_i)/k = 2m/k$.
Furthermore, $Var(X^p_i) = E[(X^p_i)^2] - E[X^p_i]^2 = \frac{1}{k}(d(v_i))^2 - (\frac{d(v_i)}{k})^2 = \frac{(d(v_i))^2}{k}(1 - 1/k)$ and
hence $Var(X^p) = \sum_{i=1}^n Var(X^p_i) = \frac{1}{k}(1 - \frac{1}{k}) \sum_{i=1}^n (d(v_i))^2 \leq \frac{1}{k}(1 - \frac{1}{k}) \sum_{i=1}^n \Delta d(v_i) =  \frac{1}{k}(1 - \frac{1}{k}) \Delta m$.

Using Bernstein's inequality, we have (for some $t > 0$):
$$\Pr(X^p > E[X^p] + t) \leq e^{-\frac{t^2}{2Var(X^p) + (2/3)bt)}}$$
where $b = \max_{1 \leq i \leq n} |X^p_i - E[X^p_i]|$.
Now, $|X^p_i - E[X^p_i]| \leq d(v_i) (1 - 1/k) \leq \Delta(1 - 1/k) = b$.

Let $\gamma>0$ and let $A$ be the event that $X^p > 2m/k +  \gamma (2m/k + \Delta)$.
Hence, for any $\gamma > 0$ and letting $t= \gamma(2m/k + \Delta)$,  we have:

\begin{align*}
  \Pr(A) &\leq e^{-\frac{t^2}{2(1/k)(1-1/k)\Delta m + (2/3)\Delta(1 - 1/k)t}}  
  \leq e^{-\frac{t^2}{\Theta(m\Delta/k + \Delta t)}}\\
  &\leq e^{-\frac{\gamma^2(2m/k + \Delta)^2}{\Theta(m\Delta/k + \Delta^2)}} \leq e^{-\gamma^2 \Theta(\frac{m}{\Delta k} + \frac{\Delta k}{m} + 1)} = O(1/n^3),
\end{align*}
 if $\gamma = \Theta(\sqrt{\log n})$.
 
 The above tail bound applies to a single machine $p$; applying a union bound over all the $k$ machines, we have 
 $X^p = \tilde{O}(m/k + \Delta)$  whp for every  machine $p \in N$.
 
 We now show (b) which will complete the proof of Part 2.
 Fix a link $\ell = (p,q)$ of the $k$-machine network. Let $X^{p}$ (resp. $X^{q}$) be defined as before, i.e., the total
 number of edges of $G$ with at least one end-vertex assigned to $p$ (resp. $q$).   Note that each such edge mapped to $p$
 has probability of $1/(k-1)$   of being mapped to link $\ell$ (independently of other edges mapped to $p$). A similar statement
 holds for edges mapped to $q$ as well.
  Let r.v. $Z^p_{\ell} $ (resp. $Z^q_{\ell}$) denote the number of edges, among those mapped to $p$ (resp. $q$),
 that are mapped to link $\ell$; the total number of edges mapped to $\ell$ is bounded by $Z^p_{\ell} + Z^q_{\ell}$. We have,  $E[Z^p_{\ell}|X^p] \leq   \lceil \frac{X^p}{k-1} \rceil$ and similarly $E[Z^q_{\ell}|X^q]
 \leq \lceil\frac{X^q}{k-1}\rceil$. We next show that $Z^p_{\ell}$ and $Z^q_{\ell}$ are both bounded by $\tilde{O}(m/k^2 + \Delta/k)$ whp which
 will complete the proof.
We  focus on $Z^p_{\ell}$; (the case of $Z^q_{\ell}$ is similar). By proof of (a),  $X^p < \Phi$ with probability at least $1 - 1/n^2$, where $\Phi = c\log n (m/k + \Delta)  $ for some sufficiently large constant $c >0$. Observe that an edge that has one endpoint mapped to $p$ is mapped to link $\ell$ independently. Hence we can apply a standard Chernoff bound~\cite{panconesi}: 
$\Pr(Z^p_{\ell} < c'\Phi/k + 1) \leq
 \Pr(X^p > \Phi) + \Pr(Z^p_{\ell} < c'\Phi/k + 1) | X^p < \Phi) \leq 1/n^2 + 2^{-c'\Phi/k + 1} \leq  1/n^2 + 2^{-3\log n + \Omega(1)} = O(1/n^2)$, 
 for a sufficiently large constant $c' > 0$. 
 
 Thus, whp, the number of edges mapped to link $\ell$ is $c'\Phi/k = \tilde{O}(m/k^2 + \Delta/k)$. Applying a union bound
 over all $k(k-1)/2$ links, yields the result.
\end{proof}
}
%\end{comment}
